/**
 * 循环队列
1. 用数组实现循环队列，
支持 enqueue、dequeue、front、isEmpty、isFull（通过 (rear+1)%maxSize == front 判断）。
测试用例：maxSize=5，enqueue (1,2,3,4)→队满→dequeue()=1→enqueue (5)→队列元素为 [2,3,4,5]。
 */

 #include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 循环队列结构体
typedef struct {
    int* data;       // 存储队列元素的数组
    int front;       // 队头指针（指向队头元素）
    int rear;        // 队尾指针（指向队尾元素的下一个位置）
    int maxSize;     // 队列最大容量
} CircularQueue;

// 初始化循环队列  没有哨兵
CircularQueue* createQueue(int maxSize) {
    CircularQueue* queue = (CircularQueue*)malloc(sizeof(CircularQueue));
    queue->maxSize = maxSize;
    queue->data = (int*)malloc(sizeof(int) * maxSize);
    queue->front = 0;
    queue->rear = 0;
    return queue;
}

// 判断队列是否为空
bool isEmpty(CircularQueue* queue) {
    return queue->front == queue->rear;
}

// 判断队列是否为满
bool isFull(CircularQueue* queue) {
    return (queue->rear + 1) % queue->maxSize == queue->front;
}

// 入队操作
bool enqueue(CircularQueue* queue, int element) {
    if (isFull(queue)) {
        return false; // 队满，入队失败
    }
    queue->data[queue->rear] = element;
    queue->rear = (queue->rear + 1) % queue->maxSize; // 循环移动队尾指针
    return true;
}

// 出队操作
int dequeue(CircularQueue* queue) {
    if (isEmpty(queue)) {
        return -1; // 队空，返回特殊值（实际应用中可根据需求调整）
    }
    int element = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->maxSize; // 循环移动队头指针
    return element;
}

// 获取队头元素
int front(CircularQueue* queue) {
    if (isEmpty(queue)) {
        return -1; // 队空，返回特殊值
    }
    return queue->data[queue->front];
}

// 打印队列元素（辅助测试用）
void printQueue(CircularQueue* queue) {
    if (isEmpty(queue)) {
        printf("队列为空\n");
        return;
    }
    printf("队列元素: [");
    int i = queue->front;
    while (i != queue->rear) {
        printf("%d", queue->data[i]);//因为没有哨兵，直接开始打印
        i = (i + 1) % queue->maxSize;
        if (i != queue->rear) {
            printf(", ");
        }
    }
    printf("]\n");
}

// 测试用例
int main() {
    int maxSize = 5;
    CircularQueue* queue = createQueue(maxSize);

    // 入队 1,2,3,4
    enqueue(queue, 1);
    enqueue(queue, 2);
    enqueue(queue, 3);
    enqueue(queue, 4);
    printf("入队1,2,3,4后: ");
    printQueue(queue); // 应输出 [1, 2, 3, 4]

    // 检查是否队满
    printf("此时队列是否满: %s\n", isFull(queue) ? "是" : "否"); // 应输出 否（因为预留了一个空位）

    // 尝试入队第5个元素（此时会满）
    bool enqueue5 = enqueue(queue, 5);
    printf("入队5是否成功: %s\n", enqueue5 ? "是" : "否"); // 应输出 否
    printf("入队5失败后队列: ");
    printQueue(queue); // 仍为 [1, 2, 3, 4]

    // 出队操作
    int dequeued = dequeue(queue);
    printf("出队元素: %d\n", dequeued); // 应输出 1

    // 再次入队5
    enqueue5 = enqueue(queue, 5);
    printf("再次入队5是否成功: %s\n", enqueue5 ? "是" : "否"); // 应输出 是
    printf("最终队列元素: ");
    printQueue(queue); // 应输出 [2, 3, 4, 5]

    // 释放内存
    free(queue->data);//！！！！！！！！！！！！！
    free(queue);//！！！！！！！！！！！！！
    return 0;
}